let dataArray = [1, 3, 9, 5, 1, 9, 104, 5];

/**
 * 交换数组中的两个数据
 * @param array
 * @param index
 * @param index1
 */
function swap(array, index, index1) {
    let temp = array[index];
    array[index] = array[index1];
    array[index1] = temp;
}

/**
 * 冒泡排序
 * @param array
 */
function bubbleSort(array) {
    let len = array.length, temp;
    for (let outer = len; outer > 0; --outer) {
        for (let inner = 0; inner < outer; inner++) {
            if (array[inner] > array[inner + 1]) {
                swap(array, inner, inner + 1);
            }
        }
    }
    return array;
}

/**
 * 选择排序
 * @param array
 * @returns {*}
 */
function selectSort(array) {
    let minIndex, len = array.length;

    for (let outer = 0; outer < len - 1; outer++) {
        minIndex = outer;
        for (let inner = outer + 1; inner < len - 1; inner++) {
            if (array[inner] < array[minIndex]) {
                minIndex = inner;
            }
        }
        swap(array, minIndex, outer);

    }
    return array;
}


/**
 * 插入排序
 * @param array
 */
function insertSort(array) {
    let len = array.length,
        temp;

    for (var i = 0; i < len; i++) {
        if (array[i] < array[i - 1]) {
            temp = array[i];
            let last = i - 1; // 记录下有序部分的最后的位置
            array[i] = array[last]; // 将有序的部分向后拓展一位

            // 比新建来的元素大的往后移动一位
            while (array[last] > temp) {
                array[last + 1] = array[last];
                last--;
            }
            array[last] = temp;
        }
    }

    return dataArray;
}


/**
 * 快速排序
 * @param array
 */
function quickSort(array) {
    if (array.length < 2) {
        return array;
    }
    let leftArray = [], rightArray = [], middleIndex = Math.floor(array.length / 2), middleVal = array[middleIndex];
    array.splice(middleIndex, 1);
    array.forEach(item => item > middleVal ? rightArray.push(item) : leftArray.push(item));
    return [...quickSort(leftArray), middleVal, ...quickSort(rightArray)];
}

// 归并排序
function merge(leftArray, rightArray) {
    let temp = [];

    while (leftArray.length && rightArray.length) {
        if (leftArray[0] < rightArray[0]) {
            temp.push(leftArray.shift());
        } else {
            temp.push(rightArray.shift());
        }
    }
    ;
    return temp.concat(leftArray, rightArray);
}

function mergeSort(array) {
    if (array.length < 2) {
        return array;
    }
    let mid = Math.floor(array.length), leftArray = array.slice(0, mid), rightArray = array.slice(mid);
    console.log(array);
    return merge(mergeSort(leftArray), mergeSort(rightArray));

}

console.log(bubbleSort(dataArray));
console.log(selectSort(dataArray));
console.log(insertSort(dataArray));
console.log(quickSort(dataArray));
console.log(mergeSort(dataArray));
